package th.retrofit.lib;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * 给定一个三角形 triangle ，找出自顶向下的最小路径和。
 *
 * 每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
 */
public class Solution120 {

    public int minimumTotal(List<List<Integer>> triangle) {
        int tSize = triangle.size();
        List<Integer> list = new ArrayList<>(tSize);
        list.add(triangle.get(0).get(0));
        for (int i = 1; i < tSize; i++) {
            List<Integer> line = triangle.get(i);
            for (int j = i; j >= 0; j--) {
                if (j == 0) {
                    list.set(j, list.get(j) + line.get(j));
                } else if (j == i) {
                    list.add(list.get(j - 1) + line.get(j));
                } else {
                    list.set(j, line.get(j) + Math.min(list.get(j), list.get(j - 1)));
                }
            }
        }
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < list.size(); i++) {
            min = Math.min(min, list.get(i));
        }
        return min;
    }

    public static void main(String[] args) {
        List<List<Integer>> triangle = new LinkedList<>();
//        List<Integer> row1 = new LinkedList<>();
//        row1.add(2);
//        List<Integer> row2 = new LinkedList<>();
//        row2.add(3);
//        row2.add(4);
//        List<Integer> row3 = new LinkedList<>();
//        row3.add(6);
//        row3.add(5);
//        row3.add(7);
//        List<Integer> row4 = new LinkedList<>();
//        row4.add(4);
//        row4.add(1);
//        row4.add(8);
//        row4.add(3);
//        triangle.add(row1);
//        triangle.add(row2);
//        triangle.add(row3);
//        triangle.add(row4);

        int[][] arr = new int[][]{
                {-7},
                {-2,1},
                {-5,-5,9},
                {-4,-5,4,4},
                {-6,-6,2,-1,-5},
                {3,7,8,-3,7,-9},
                {-9,-1,-9,6,9,0,7},
                {-7,0,-6,-8,7,1,-4,9},
                {-3,2,-6,-9,-7,-6,-9,4,0},
                {-8,-6,-3,-9,-2,-6,7,-5,0,7},
                {-9,-1,-2,4,-2,4,4,-1,2,-5,5},
                {1,1,-6,1,-2,-4,4,-2,6,-6,0,6},
                {-3,-3,-6,-2,-6,-2,7,-9,-5,-7,-5,5,1}};
        for (int i = 0; i < arr.length; i++) {
            List<Integer> list = new ArrayList<>();
            for (int j = 0; j < arr[i].length; j++) {
                list.add(arr[i][j]);
            }
            triangle.add(list);
        }
        System.out.println(new Solution120().minimumTotal(triangle));
    }

}
